#include "list.h"

template <typename T> void List<T>::init()
{
	header = new ListNode<T>;
	trailer = new ListNode<T>;

	header->succ = trailer;
	header->pred = NULL;

	trailer->pred = header;
	trailer->succ = NULL;

	_size = 0;
}

//重载[]操作符以支持循秩访问，O(n)
template <typename T> T& List<T>::operator[](Rank r) const {	
	ListNodePosi(T) p = first();
	while(0 < r--)
		p = p->succ;
	return p->data;
}

//区间查找>前向查找O(n)
template <typename T> 
ListNodePosi(T) List<T>::find(const T &e,int n,ListNode<T> *p) const {
	while(0 < n--)
		if(e == (p = p->pred)->data) return p;
	return NULL;
}

//多种节点插入操作
template <typename T>
ListNodePosi(T) List<T>::insertAsFirst(const T &e) {
	++_size;
	return header->insertAsSucc(e);
}

template <typename T>
ListNodePosi(T) List<T>::insertAsLast(const T &e) {
	++_size;
	return trailer->insertAsPred(e);
}

template <typename T>
ListNodePosi(T) List<T>::insertA(ListNode<T> *p,const T &e) {
	++_size;
	return p->insertAsSucc(e);
}

template <typename T>
ListNodePosi(T) List<T>::insertB(ListNode<T> *p,const T &e) {
	++_size;
	return p->insertAsPred(e);
}


//复制构造
template <typename T>
void List<T>::copyNodes(ListNodePosi(T) p,int n) {
	init();
	while(n--) {
		insertAsLast(p->data);
		p = p->succ;
	}
}

template <typename T>
List<T>::List(ListNodePosi(T) p,int n) {
	copyNodes(p,n);
}

template <typename T>
List<T>::List(List<T> const &L) {
	copyNodes(L.first(),L._size);
}

template <typename T>
List<T>::List(List<T> const &L,int r,int n) {
	copyNodes(L[r],n);
}

//删除节点O(n)
template <typename T>
T List<T>::remove(ListNode<T> *p) {
	T e = p->data;
	p->pred->succ = p->succ;
	p->succ->pred = p->pred;

	--_size;
	delete p;

	return e;
}


//析构函数

template <typename T>
List<T>::~List() {
	clear();
	delete header;
	delete trailer;
}

/*删除所有的节点，返回链表大小*/
template <typename T>
int List<T>::clear() {
	int oldSize = _size;
	while(0 < _size)
		remove(header->succ);

	return oldSize;
}

//唯一化：剔除无序列表中的重复节点,返回被删除元素总数
//对于每个节点，调用前向查找函数来搜索它前面的所有和它
//相同的节点。(O(n^2)) 
template <typename T>
int List<T>::deduplicate() {
	if(_size < 2)
		return 0;
	int oldSize = _size;
	ListNodePosi(T)	p = header;
	Rank r = 0;
	while(trailer != (p = p->succ)) {
		ListNodePosi(T) q = find(p->data,r,p);
		q ? remove(q) : r++;
	}

	return oldSize - _size;
}

//遍历

template <typename T>
void List<T>::traverse(void (*visit)( T& )) {	//函数指针机制
	for(ListNodePosi(T) p = header->succ;p != trailer;p = p->succ)
		visit(p->data);
}

template <typename T> template <typename VST>
void List<T>::traverse(VST &visit) {
	for(ListNodePosi(T) p = header->succ;p != trailer;p = p->succ)
		visit(p->data);
}

//有序表的特有操作
//
//唯一化：剔除重复节点
template <typename T>
int List<T>::uniquify(){
	if(_size < 2)
		return 0;
	int oldSize = _size;

	ListNodePosi(T) p = first();
	ListNodePosi(T) q = p->succ;

	while(trailer != (q = p->succ)) {
		if(p->data == q->data) {
			remove(q);
		}
		else 
			p = q;
	}

	return oldSize - _size;
}


//有序表查找,从p前向查找n个元素，找到不大于e的元素的位置
template <typename T>
ListNodePosi(T) List<T>::search(const T &e,int n,ListNode<T> *p) const {
	while(0 <= n--){
		if(((p = p->pred)->data) <= e)
			break;
	}

	return p;
}	//如果该区间没有不大于e的节点，则返回左区界


